"""
作者：马宇哲
时间：2024.5.11
功能性描述：算法设计与分析的第一次作业，负责部分：二分归并排序
"""

"""
作者随笔：这里merge_sort是主要函数，由merge_sort管理，每次递归使用merge函数进行排序
"""


# 二分归并排序算法函数
def merge_sort(array):
    """
    该函数主要是配置游标和判断游标是否到达数组末尾，数组由这里进入（算法入口）
    """
    # 这里表示分区到最后一个元素
    if len(array) <= 1:
        # 这里是最后一个元素（视为排好序的），直接返回
        return array

    mid = len(array) // 2
    # 左面的游标指向数组的前半部分，这里游标定位在最半边的最开始的位置
    left = merge_sort(array[:mid])
    # 右面的游标指向数组的后半部分，这里游标定位在右半边的最开始的位置，即mid
    right = merge_sort(array[mid:])

    # 每次返回排好序的，所以最后一次排好序的返回，直接调用即可
    return merge(left, right)
    pass


def merge(left, right):
    """
    该函数主要是合并两个有序数组
    """
    # 这里表示合并两个有序数组
    result = []
    # 定义两个操作游标
    i = j = 0

    # 确保索引分别在两个数组范围内，这里循环内是二分归并排序的核心算法
    """
    这里简单给出下面的代码的解释：
    对merge_sort函数传过来的数组进行拆解，由于这里是递归操作每一部分都是排好序的，
    这里进行操作的时候两部分都是排好序的，所以最终的结果就是使得两部分合并为一个有序数组
    """
    while i < len(left) and j < len(right):
        # 第一种情况表示左边的操作游标指向的元素小于右边的操作游标指向的元素
        if left[i] < right[j]:
            # 左面指向的元素小于右边的指向的元素，则将左面的元素添加到结果数组中
            result.append(left[i])
            i += 1
            pass
        else:
            result.append(right[j])
            j += 1
            pass
        pass

    # 每次排好序后（2->1）放到result数组中，为下一次的合并做准备
    """
    这里实际上是传入到merge_sort里面，成为下一次划分的部分数组
    """
    result.extend(left[i:])
    result.extend(right[j:])

    return result
    pass
